package List;



public class DulLinkList implements IList {
	// 头指针
	private DulNode head;
	// 链表长度
	private int length;

	// 初始化双向链表
	public DulLinkList() {
		this.head = new DulNode(null);
		this.head.setNext(null);
		this.head.setPrior(null);
		this.length=0;
	}

	/**
	 * 获取第i个节点
	 * @param i 节点位置,取值范围[0,n-1]
	 * @return {@link DulNode}类Object
	 */
	private DulNode getNodeAt(int i) throws ArrayIndexOutOfBoundsException {
		// 检查下标i的合法性
		if(i<0 || i>=this.length) {
			throw new ArrayIndexOutOfBoundsException(i);
		}
		// 确定第i个节点的位置,使用引用变量q标记
		DulNode q = this.head;
		for(int moveCnt=0;moveCnt<=i;moveCnt++) {
			q = q.getNext();
		}
		return q;
	}

	/**
	 * 获取第i个元素
	 */
	@Override
	public Object get(int i) throws Exception {
		DulNode q = this.getNodeAt(i);
		return q.getData();
	}

	@Override
	public void insert(Object x) throws Exception {
		DulNode q = this.head;
		while(q.getNext() != null) {
			q = q.getNext();
		}
		// 新构造一个节点
		DulNode newDulNode = new DulNode(x);
		// 插入节点
		q.setNext(newDulNode);
		newDulNode.setPrior(q);
		// 链表长度＋1
		this.length++;
	}

	@Override
	public void insert(int i, Object x) throws Exception {
		// 空表写入第1个数据
		if(this.length == 0 && i == 0) {
			this.insert(x);
			return;
		}
		// 检查位置参数i是否合法
		if(i < 0 || i >= this.length) {
			throw new ArrayIndexOutOfBoundsException(i);
		}
		// 确定第i-1个节点的位置,使用引用变量q标记
		DulNode q = this.getNodeAt(i-1);
		// q的下一个节点,第i个节点
		DulNode p = q.getNext();
		// 构造新节点存储数据X
		DulNode newDulNode = new DulNode(x);
		// 顺向插入新节点
		newDulNode.setNext(p);
		q.setNext(newDulNode);
		// 反向插入新节点
		newDulNode.setPrior(q);
		p.setPrior(newDulNode);
		// 链表长度加1
		this.length++;
	}

	@Override
	public Object remove(int i) throws Exception {
		// 1、判定i的合法性
		if (i < 0 || i >= this.length) {
			throw new ArrayIndexOutOfBoundsException(i);
		}
		// 2、确定第i个节点,用temp标记
		DulNode temp = this.getNodeAt(i);
		// 3、找到temp前一个节点和后一个节点,分别用q、p标记
		DulNode q=temp.getPrior();
		DulNode p=temp.getNext();
		// 4、删除节点
		q.setNext(p);
		if(p!=null) {
			p.setPrior(q);
		}
		temp.setNext(null);
		temp.setPrior(null);
		// 5、链表长度减1
		this.length--;
		return temp.getData();
	}

	@Override
	public int indexOf(Object x) {
		// 默认找不到元素X,默认返回值为-1
		int result = -1;
		// 查找元素: 遍历链表每一个节点进行比较（查找）
		DulNode temp = this.head.getNext();
		int index = 0;
		while (temp != null) {
			if (temp.getData().equals(x)) {
				result = index;
				break;
			}
			index++;
			temp = temp.getNext();
		}
		return result;
	}

	@Override
	public void display() {
		DulNode temp = this.head.getNext();
		System.out.print("[");
		while (temp != null) {
			if (temp == this.head.getNext()) {
				System.out.print(temp.getData());
			} else {
				System.out.print(",");
				System.out.print(temp.getData());
			}
			temp = temp.getNext();
		}
		System.out.println("]");
	}

}